package minijava;

import java.util.LinkedList;
import java.util.Vector;
import java.lang.Integer;

public class Graph{
    protected Vector< LinkedList<Integer> > vertices;
    private LinkedList<Integer> cycle;

    public Graph(){
	vertices = new Vector< LinkedList<Integer> >(10, 10);
	cycle = new LinkedList<Integer>();
    }

    public void addVertex(){
	vertices.add(new LinkedList<Integer>());
    }

    public void addEdge(int s, int d){
	LinkedList<Integer> edges = vertices.elementAt(s);
	edges.add(new Integer(d));
    }

    public LinkedList<Integer> findCycle(){
	cycle.clear();
	int n = vertices.size();
	int[] state = new int[n];
	int[] last = new int[n];
	if(n == 0)
	    return null;
	for(int i=0; i<n; i++){
	    state[i] = 0;
	    last[i] = -1;
	}
	for(int i=0; i<n; i++){
	    if(state[i] == 0){
		state[i] = 1;
		if(findCycle(i, state, last) == true)
		    return cycle;
	    }
	}
	return null;
    }
    private boolean findCycle(int vId, int[] state, int[] last){
	LinkedList<Integer> neighbors = vertices.elementAt(vId);
	for(Integer i : neighbors){
	    if(state[i]==0){
		last[i] = vId;
		state[i] = 1;
		if(findCycle(i, state, last) == true)
		    return true;
	    }else if(state[i]==1){
		int j = vId;
		do{
		    cycle.add(new Integer(j));
		    j = last[j];
		}while(j != i);
		cycle.add(new Integer(i));
		return true;
	    }
	}
	state[vId] = 2;
	return false;
    }
}
